Modern analog-to-digital converters (ADCs) used in radio frequency receiver applications can operate at very high speeds, such as at 3 GHz. However, the fast Fourier transform chip, based on a complex transformation principle, following many known ADCs in digital signal receiver applications, cannot operate at such high speeds due to the complexity of computing the number of sample points examined. The conventional approach to building a wideband digital receiver is to use a polyphase filter to slow down the operation speed of the fast Fourier transform. A specific example to illustrate using a polyphase filter to slow down operation of the fast Fourier transform follows.
The ADC used in this example operates at 3 GHz with 8 bits. A fast Fourier transform is performed on 256 points of digitized data. This fast Fourier transform operation can be written can be written as                               X          ⁡                      (            k            )                          =                              ∑                          n              =              0                                      N              -              1                                ⁢                                    x              ⁡                              (                n                )                                      ⁢                          ⅇ                                                                    -                    j2π                                    ⁢                                                                          ⁢                  kn                                N                                                                        (        1        )            where x(n) is the digitized input data and N=256. If the output frequency is decimated by 8, k=0, 8, 16, . . . 248 are kept. That is, there are a total of 32 (256/8) outputs. The result from Eq. 1 can be written as                                                                         X                ⁡                                  (                  0                  )                                            =                            ⁢                                                ∑                                      n                    =                    0                                    255                                ⁢                                  x                  ⁡                                      (                    n                    )                                                                                                                                          X                ⁡                                  (                  8                  )                                            =                            ⁢                                                ∑                                      n                    =                    0                                    255                                ⁢                                                      x                    ⁡                                          (                      n                      )                                                        ⁢                                      ⅇ                                                                                            -                          j2π8                                                ⁢                                                                                                  ⁢                        n                                            256                                                                                                                                                              X                ⁡                                  (                  16                  )                                            =                            ⁢                                                ∑                                      n                    =                    0                                    255                                ⁢                                                      x                    ⁡                                          (                      n                      )                                                        ⁢                                      ⅇ                                                                                            -                          j2π16                                                ⁢                                                                                                  ⁢                        n                                            256                                                                                                                                              ⋯              ⁢                                                                                                                                      X                ⁡                                  (                  248                  )                                            =                            ⁢                                                ∑                                      n                    =                    0                                    255                                ⁢                                                      x                    ⁡                                          (                      n                      )                                                        ⁢                                      ⅇ                                                                                            -                          j2π248                                                ⁢                                                                                                  ⁢                        n                                            256                                                                                                                              (        2        )            First, arbitrarily consider two frequency components k=16 and k=248 and rewrite them in slightly different form. The results are                                                                         X                ⁡                                  (                  16                  )                                            =                            ⁢                                                                    ∑                                          n                      =                      0                                        255                                    ⁢                                                            x                      ⁡                                              (                        n                        )                                                              ⁢                                          ⅇ                                                                                                    -                            j2π16                                                    ⁢                                                                                                          ⁢                          n                                                256                                                                                            =                                                      ∑                                          n                      =                      0                                        255                                    ⁢                                                            x                      ⁡                                              (                        n                        )                                                              ⁢                                          ⅇ                                                                                                    -                            j2π2                                                    ⁢                                                                                                          ⁢                          n                                                32                                                                                                                                                                    =                            ⁢                                                [                                                            x                      ⁡                                              (                        0                        )                                                              +                                          x                      ⁡                                              (                        32                        )                                                              +                                          x                      ⁡                                              (                        64                        )                                                              +                    ⋯                    +                                          x                      ⁡                                              (                        224                        )                                                                              ]                                +                                                                                                      ⁢                                                                    [                                                                  x                        ⁡                                                  (                          1                          )                                                                    +                                              x                        ⁡                                                  (                          33                          )                                                                    +                                              x                        ⁡                                                  (                          65                          )                                                                    +                      ⋯                      +                                              x                        ⁡                                                  (                          225                          )                                                                                      ]                                    ⁢                                      ⅇ                                                                                            -                          j2π2                                                ⁢                                                                                                  ⁢                        n                                            32                                                                      +                                                                                                      ⁢                                                                    [                                                                  x                        ⁡                                                  (                          2                          )                                                                    +                                              x                        ⁡                                                  (                          34                          )                                                                    +                                              x                        ⁡                                                  (                          66                          )                                                                    +                      ⋯                      +                                              x                        ⁡                                                  (                          226                          )                                                                                      ]                                    ⁢                                      ⅇ                                                                                            -                          j2π2                                                ×                        2                                            32                                                                      +                ⋯                +                                                                                                      ⁢                                                [                                                            x                      ⁡                                              (                        31                        )                                                              +                                          x                      ⁡                                              (                        63                        )                                                              +                                          x                      ⁡                                              (                        95                        )                                                              +                    ⋯                    +                                          x                      ⁡                                              (                        255                        )                                                                              ]                                ⁢                                  ⅇ                                                                                    -                        j2π2                                            ×                      31                                        32                                                                                                          (        3        )            and                                                                         X                ⁡                                  (                  248                  )                                            =                            ⁢                                                                    ∑                                          n                      =                      0                                        255                                    ⁢                                                            x                      ⁡                                              (                        n                        )                                                              ⁢                                          ⅇ                                                                                                    -                            j2π248                                                    ⁢                                                                                                          ⁢                          n                                                256                                                                                            =                                                      ∑                                          n                      =                      0                                        255                                    ⁢                                                            x                      ⁡                                              (                        n                        )                                                              ⁢                                          ⅇ                                                                                                    -                            j2π8                                                    ⁢                                                                                                          ⁢                          n                                                32                                                                                                                                                                    =                            ⁢                                                [                                                            x                      ⁡                                              (                        0                        )                                                              +                                          x                      ⁡                                              (                        32                        )                                                              +                                          x                      ⁡                                              (                        64                        )                                                              +                    ⋯                    +                                          x                      ⁡                                              (                        224                        )                                                                              ]                                +                                                                                                      ⁢                                                                    [                                                                  x                        ⁡                                                  (                          1                          )                                                                    +                                              x                        ⁡                                                  (                          33                          )                                                                    +                                              x                        ⁡                                                  (                          65                          )                                                                    +                      ⋯                      +                                              x                        ⁡                                                  (                          225                          )                                                                                      ]                                    ⁢                                      ⅇ                                                                  -                        j2π31                                            32                                                                      +                                                                                                      ⁢                                                                    [                                                                  x                        ⁡                                                  (                          2                          )                                                                    +                                              x                        ⁡                                                  (                          34                          )                                                                    +                                              x                        ⁡                                                  (                          66                          )                                                                    +                      ⋯                      +                                              x                        ⁡                                                  (                          226                          )                                                                                      ]                                    ⁢                                      ⅇ                                                                                            -                          j2π31                                                ×                        2                                            32                                                                      +                ⋯                +                                                                                                      ⁢                                                [                                                            x                      ⁡                                              (                        31                        )                                                              +                                          x                      ⁡                                              (                        63                        )                                                              +                                          x                      ⁡                                              (                        95                        )                                                              +                    ⋯                    +                                          x                      ⁡                                              (                        255                        )                                                                              ]                                ⁢                                  ⅇ                                                                                    -                        j2π31                                            ×                      31                                        32                                                                                                          (        4        )            In the above equations the relation of e−j2πn=1 when n=integer is used. Now consider a new quantity, y(n) as                                                                         y                ⁡                                  (                  n                  )                                            =                            ⁢                                                x                  ⁡                                      (                    n                    )                                                  +                                  x                  ⁡                                      (                                          n                      +                      32                                        )                                                  +                                  x                  ⁡                                      (                                          n                      +                      64                                        )                                                  +                ⋯                +                                  x                  ⁡                                      (                                          n                      +                      224                                        )                                                                                                                          =                            ⁢                                                ∑                                      m                    =                    0                                    7                                ⁢                                  x                  ⁡                                      (                                          n                      +                                              32                        ⁢                        m                                                              )                                                                                                          (        5        )            where n=0 to 31. The quantity y(n) represents the values in the bracket of Eqs (3) and (4). Each y value contains a total of 8 data points. This operation is graphically represented in FIG. 1. In FIG. 1, the 256 input data points shown at 100 are divided into eight 32-point sections, two of which are shown at 101. The beginning data point of each section is shown. These eight sections are shown stacked at 102 and summed vertically as shown at 103. The results are the 32 y(n) values.
Using these y(n) values, the results from Eq. (2) can be rewritten as                                                                         X                ⁡                                  (                  0                  )                                            =                            ⁢                                                ∑                                      n                    =                    0                                    31                                ⁢                                  y                  ⁡                                      (                    n                    )                                                                                                                                          X                ⁡                                  (                  8                  )                                            =                            ⁢                                                y                  ⁡                                      (                    0                    )                                                  +                                                      y                    ⁡                                          (                      1                      )                                                        ⁢                                      ⅇ                                                                  -                        j2π                                            32                                                                      +                                                      y                    ⁡                                          (                      2                      )                                                        ⁢                                      ⅇ                                                                                            -                          j2                                                ⁢                                                                                                  ⁢                        π                        ⁢                                                                                                  ⁢                        2                                            32                                                                      +                ⋯                +                                                      y                    ⁡                                          (                      31                      )                                                        ⁢                                      ⅇ                                                                  -                        j2π31                                            32                                                                                                                                              =                            ⁢                                                ∑                                      n                    =                    0                                    31                                ⁢                                                      y                    ⁡                                          (                      n                      )                                                        ⁢                                      ⅇ                                                                                            -                          j2π                                                ⁢                                                                                                  ⁢                        n                                            32                                                                                                                                                              X                ⁡                                  (                  16                  )                                            =                            ⁢                                                y                  ⁡                                      (                    0                    )                                                  +                                                      y                    ⁡                                          (                      1                      )                                                        ⁢                                      ⅇ                                                                  -                        j2π2                                            32                                                                      +                                                      y                    ⁡                                          (                      2                      )                                                        ⁢                                      ⅇ                                                                                            -                          j2                                                ⁢                                                                                                  ⁢                        π                        ⁢                                                                                                  ⁢                        2                        ×                        2                                            32                                                                      +                ⋯                +                                                      y                    ⁡                                          (                      31                      )                                                        ⁢                                      ⅇ                                                                                            -                          j2π2                                                ×                        31                                            32                                                                                                                                              =                            ⁢                                                ∑                                      n                    =                    0                                    31                                ⁢                                                      y                    ⁡                                          (                      n                      )                                                        ⁢                                      ⅇ                                                                                            -                          j2π                                                ⁢                                                                                                  ⁢                        2                        ⁢                        n                                            32                                                                                                                                              ⋯              ⁢                                                                                                                                      X                ⁡                                  (                  248                  )                                            =                            ⁢                                                y                  ⁡                                      (                    0                    )                                                  +                                                      y                    ⁡                                          (                      1                      )                                                        ⁢                                      ⅇ                                                                  -                        j2π31                                            32                                                                      +                                                      y                    ⁡                                          (                      2                      )                                                        ⁢                                      ⅇ                                                                                            -                          j2                                                ⁢                                                                                                  ⁢                        π                        ⁢                                                                                                  ⁢                        31                        ×                        2                                            32                                                                      +                ⋯                +                                                      y                    ⁡                                          (                      31                      )                                                        ⁢                                      ⅇ                                                                                            -                          j2π31                                                ×                        31                                            32                                                                                                                                              =                            ⁢                                                ∑                                      n                    =                    0                                    31                                ⁢                                                      y                    ⁡                                          (                      n                      )                                                        ⁢                                      ⅇ                                                                                            -                          j2π                                                ⁢                                                                                                  ⁢                        31                        ⁢                        n                                            32                                                                                                                              (        6        )            All these equations can be written into one as                               X          ⁡                      (                          8              ⁢              k                        )                          =                              ∑                          n              =              0                        31                    ⁢                                    y              ⁡                              (                n                )                                      ⁢                          ⅇ                                                                    -                    j2π                                    ⁢                                                                          ⁢                  kn                                32                                                                        (        7        )            where k=0, 1, 2, . . . , 31; and n=0, 1, 2, . . . , 31.
The output X(8k) can be relabeled as Y(k), thus, Eq. 7 can be written as                               Y          ⁡                      (            k            )                          =                              ∑                          n              =              0                        31                    ⁢                                    y              ⁡                              (                n                )                                      ⁢                          ⅇ                                                                    -                    j2π                                    ⁢                                                                          ⁢                  kn                                32                                                                        (        8        )            Equation 8 represents a 32-point fast Fourier transform. In order to obtain the outputs of a 256-point fast Fourier transform decimated by 8 on the output, a 32-point fast Fourier transform can achieve the goal. Thus, the design of the fast Fourier transform can be simplified. However, the input signal must be manipulated in order to obtain the desired result.
Further, consider that if one wants to perform an N-point fast Fourier transform and the outputs in the frequency domain are decimated by M, one can achieve the goal by performing a N/M point fast Fourier transform. For this example, a new input format y(n) must be built first. The generalization of the y(n) can be written as                               y          ⁡                      (            n            )                          =                              ∑                          m              =              0                                      M              -              1                                ⁢                      x            ⁡                          (                              n                +                                  mN                  /                  M                                            )                                                          (        9        )            where n=0, 1, 2, . . . (N/M)−1. The outputs in the frequency domain can be obtained as                               X          ⁡                      (            k            )                          =                              ∑                          n              =              0                                                      (                                  N                  /                  M                                )                            -              1                                ⁢                                    y              ⁡                              (                n                )                                      ⁢                          ⅇ                                                                    -                    j2π                                    ⁢                                                                          ⁢                  kn                                                  N                  /                  M                                                                                        (        10        )            
This illustrates that when the fast Fourier transform outputs are decimated by M, the outputs can be obtained from N/M point fast Fourier transform. This allows the design of a fast Fourier transform chip to be simplified tremendously.
If the fast Fourier transform uses 256 data points but only every one-eighth of the outputs are kept, there are a total of 32 outputs, and 16 of them carry redundant information. Therefore, only 16 outputs are displayed in FIG. 2. In FIG. 2, the y-axis at 201 represents amplitude in decibels and the x-axis represents frequency. Each filter output is represented by a sinc function, two of which are shown at 200. Only a few side lobes are shown in FIG. 2 and the highest two are only 13 dB below the main lobe, shown at 203. This filter bank has many holes. If an input signal falls in one of the holes, the receiver will miss it entirely. The shape of this filter is definitely unacceptable.
To widen the individual filters and at the same time suppress the side lobes, a window (or weighting) function can be applied to the input data. There are many different window functions. The one used in the present example is the Parks-McClellan window because it can provide the desired frequency response. The relative amplitude of the window function is shown in FIGS. 3a and 3b. In FIGS. 3a and 3b, the y-axis represents amplitude, in FIG. 3a the x-axis represents time sample at 301 and in FIG. 3b the x-axis at 302 represents frequency. FIG. 3b shows the corresponding frequency domain response with very low pass band ripples at 304 and side lobes lower than 70 dB. This is a desirable filter shape.
The input data x(n) will be modified by the window function h(n). The resulting data xm(n) used as the input of the fast Fourier transform can be written asxm(n)=x(n)h(n)  (11)where n=0, 1, 2, . . . , 255. As stated previously, the outputs are decimated by 8. Under this condition the modified data can be used in Equation (5) to find the y(n) as                                           y            ⁡                          (              n              )                                ⁢                                    ∑                              m                =                0                            7                        ⁢                                          x                m                            ⁡                              (                                  n                  +                                      32                    ⁢                    m                                                  )                                                    =                              ∑                          m              =              0                        7                    ⁢                                    x              ⁡                              (                                  n                  +                                      32                    ⁢                    m                                                  )                                      ⁢                          h              ⁡                              (                                  n                  +                                      32                    ⁢                    m                                                  )                                                                        (        12        )            where n=0, 1, 2, . . . (N/M)−1. A few y(n) terms are written asy(0)=x(0)h(0)+x(32)h(32)+ . . . +x(224)h(224)y(1)=x(1)h(1)+x(33)h(33)+ . . . +x(225)h(225)                . . .y(31)=x(31)h(31)+x(63)h(63)+ . . . +x(255)h(255)  (13)        
If a 32-point fast Fourier transform is performed on these y(n) values, 16 individual filters will be generated. Each filter shape is as shown in FIG. 3b. 
Now let us consider in more detail the process to generate the y(n) values. Each of these values can be generated from the convolution output of a filter with the input signal. The 256-point window function in the time domain can be written ash(n)=h(255)δ(n)+h(254)δ(n−1)+h(253)δ(n−2)+ . . . +h(0)δ(n−255)  (14)where the δ function indicates the h(n) value occurs at time n. The impulse sequence of the filter is written in an inverse way. This impulse function can generate the results from Equation (13) through convolution with the input signal. Since the window function shown in FIG. 3a is symmetric in the time domain, this inverse is just a subscript change. The weighting function can be decimated by 32 and the results are 32 individual filters and each filter has eight taps. This filter decimation is often referred to as the polyphase filter. Each of the 32 filters has the response as indicated below.h0(n)=h(224)δ(n)+h(192)δ(n−1)+h(160)δ(n−2)+ . . . +h(0)δ(n−7)h1(n)=h(225)δ(n)+h(193)δ(n−1)+h(161)δ(n−2)+ . . . +h(1)δ(n−7)    . . .h31(n)=h(255)δ(n)+h(223)δ(n−1)+h(191)δ(n−2)+ . . . +h(31)δ(n−7)  (15)These filters must convolve with the proper input data to obtain the result in Equation (13). In order to obtain the correct data format, the input data must be decimated by 32 also. When the decimated input signal and the decimated filter are convolved and reaching steady state, the output is equal to the result of Equation (13).
The next time the 32-point fast Fourier transform is performed, the input y(n) values to the fast Fourier transform arey(0)=x(32)h(0)+x(64)h(32)+ . . . +x(256)h(224)y(1)=x(33)h(1)+x(65)h(33)+ . . . +x(257)h(225)                . . .y(31)=x(63)h(31)+x(95)h(63)+ . . . +x(287)h(255)  (16)In Eq. 16, the first data point is x(32), thus, the input is shifted 32 points. The hardware to accomplish this goal is shown in FIG. 4. In FIG. 4, there are 32 filters, shown at 400 and each filter has 8 taps. Two cycles of input data are shown at 401 and each cycle contains 32 data points. The outputs at 402 are shown as y(n) and they are used as the input of the fast Fourier transform. The final results in the frequency domain at 403 are represented by Y(k). In this case the inputs are decimated by 32 and the final frequency domain also has 32 outputs. The input data are shifted 32 points, which is also the output frequency bin number. This case is referred to as the critically sampled case. A critically sampled case is that the number of output frequency bin equals to the input data shift. This means that the output sampling rate is 1/M times the input sampling rate where M is the number of input data point shifted.        
Each individual filter in FIG. 4 is a finite impulse response (FIR) filter. Filter number 0 with y(0) is shown in FIG. 5. In FIG. 5, the decimated input data points are shown at 500. When the input signal reaches steady state, the output of the filter contains 8 terms. The first and second consecutive filter outputs after steady state are also listed and shown at 501 and 502. The lower line 502 represents the first output, which matches the y(0) output of Equation (13). The upper line 501 represents the second time output where the input data are shifted by 32 points. This result match the y(0) output from Equation (16). The rest of the filter outputs can be obtained in a similar manner.
The shape of the filter bank is shown in FIG. 6. This filter bank has a dynamic range of close to 75 dB, shown at 602, with a bandwidth of about 93.75 MHz, one of which is shown at 603. In these wide band filters, simultaneous signals should also be considered since the probability of two signals falling into one channel is high.
To improve the single signal frequency resolution, a phase comparator is used at every output. For example, there are two signals and both are in channel 5 as shown in FIG. 7 at 700, with channel 5 shown at 701. In the graph of FIG. 7, the y-axis at 704 shows the filter response and the x-axis at 705 represents the frequency. Signal 1 is close to channel 4 shown at 702 and signal 2 is close to channel 6 shown at 703. The signals are separated by ¼ of the channel width and signal 1 is 20 dB stronger than signal 2. The three phase comparators are used to measure the two output frequencies. Phase comparator in channel 4 measures the frequency of signal 1 and phase comparator in channel 6 measures the frequency of signal 2. Channel 5 contains both signals and it is difficult to measure them in one channel. In this design, channels 4 and 6, represented at 702 and 703, respectively, can measure the two frequencies, thus, it is not necessary to obtain the frequency from channel 5. It is desirable to process two signals in one channel by one processor rather than three. The present invention can accomplish this goal.